package com.race;

/**
 * 快排
 * Created by sid on 17/11/21.
 */
public class QuickSort {

    public static void main(String[] args) {
        float[] floats = {2, 4, 1, 3, 0, 7, 1.5f, -2.7f};
        System.out.println("before------");
        for (float f : floats) {
            System.out.print(f + " ");
        }
        System.out.println();

        quickSort(floats, 0, floats.length - 1);

        System.out.println("end------");
        for (float f : floats) {
            System.out.print(f + " ");
        }
        System.out.println();
    }

    private QuickSort() throws Exception {
        throw new Exception("singleton");
    }

    private static void quickSort(float[] arrays, int start, int end) {
        if (start >= end) {
            return;
        }

        int middleIndex = findMiddleIndex(arrays, start, end);
        quickSort(arrays, start, middleIndex - 1);
        quickSort(arrays, middleIndex + 1, end);
    }

    private static int findMiddleIndex(float[] arrays, int start, int end) {
        float middleValue = arrays[start];
        while (start < end) {
            while (arrays[end] >= middleValue && start < end) {
                end--;
            }

            arrays[start] = arrays[end];

            while (arrays[start] <= middleValue && start < end) {
                start++;
            }

            arrays[end] = arrays[start];
        }
        arrays[start] = middleValue;
        return start;
    }

}
